【题解】 [HAOI2018]苹果树组合数学 loj2526

有趣的题目，可爱的传送门：戳这呢=￣ω￣=

刚开始往概率 $\rm{DP}$ 想了，发现对于一个点的概率是好算，但是如果求贡献的话就会很难办。最后万般无赖的点开了题解，发现居然是……组合数学？其实和 $\rm{DP}$ 没有半毛钱关系。

我们考虑一个节点 $i$ ，我们枚举其子树大小 $j$ 。现在考虑最终有多少种合法的情况可以使得 $i$ 的子树大小恰好为 $j$ 。

易知节点数为 $n$ 的二叉树的总形态数为 $n!$ ，而且 $i$ 子树下的所有节点的编号一定要大于 $i$ ，我们考虑”先将 $i$ 子树构造出来再填入节点”的过程，子树的形态数显然为 $j!$ ，然后我们只能选剩下的 $n-i$ 个节点(编号要比 $i$ 大) ，填入剩下的 $j-1$ 个位置( $i$ 占了一个位置) ，显然这样的方案数为 $C_{n-i}^{j-1}$ 。

这样的一个 $i$ ，其子树大小为 $j$ ，那么它可以做出多少贡献呢？考虑 $fa_i \Rightarrow i$ 这条边会经过多少次，显然是 $j\cdot(n-j)$ 次( $j$ 为子树节点个数，$n-j$ 为上面的节点个数) ，也就是说这样的方案可以造成 $j\cdot (n-j)$ 的贡献。

那么现在 $i$ 的子树得到确定了，我们将 $i$ 以及其子树看做一个点，我们考虑 $1$ 到 $i$ 这些节点，它们可以以任意形态组成一棵树，方案数是 $i!$ 。

接着我们需要将剩下的 $n-j-(i-1)$ 个节点挂到树上去。对于第 $i$ 个挂到树上的点，它有 $i$ 个位置可以挂。但是因为 $i$ 一定要占一个位置，所以这个节点只有 $i-1$ 个位置可以挂了，第二个多出来的节点就有 $i$ 个位置可以挂……第 $k$ 个显然有 $i-2+k$ 个位置可以挂。也就是说这些点挂上去的总方案数为 $\prod\limits_{k=1}^{n-j-(i-1)} (i-2+k)$ 。

将上面的乘起来就是这一组 $i,j$ 对答案造成的贡献了：

$j!\cdot C_{n-i}^{j-1}\cdot j\cdot (n-j)\cdot i!\cdot\prod\limits_{k=1}^{n-j-(i-1)} (i-2+k)$

$\prod\limits_{k=1}^{n-j-(i-1)} (i-2+k)$ 比较不好计算，但是简单的变化后发现这个是和 $(n-j-1)!/(i-2)!$ 等价的，我们带进原式子。

$j!\cdot C_{n-i}^{j-1}\cdot j\cdot (n-j)\cdot i!\cdot(n-j-1)!/(i-2)!\\\\=j!\cdot C_{n-i}^{j-1}\cdot j\cdot (n-j)\cdot i\cdot (i-1)\cdot(n-j-1)!\\\\=j!\cdot C_{n-i}^{j-1}\cdot j\cdot i\cdot (i-1)\cdot (n-j)!$

这样就很好算了，我们预处理组合数和阶乘，上面的式子 $O(1)$ 算~

代码很短。

Code：

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=2e3+2;
const int inf=1e9+9;

int n,p,ans,fac[N],C[N][N];

namespace OI {
    void pls(int&x,int y) {x+=y;x%=p;}
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace OI;

int main() {
    IN(n),IN(p);
    fac[1]=1;
    for(int i=2;i<=n;++i) fac[i]=1ll*fac[i-1]*i%p;
    for(int i=0;i<=n;++i) C[i][0]=1;
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n-i+1;++j)
            pls(ans,(ll)fac[j]*fac[n-j]%p*C[n-i][j-1]%p*(i*(i-1))%p*j%p);
    printf("%d\n",ans);
    return 0;
}

本文标题:【题解】 [HAOI2018]苹果树组合数学 loj2526

文章作者:Qiuly

发布时间:2019年05月05日 - 00:00

最后更新:2019年05月06日 - 13:23

原始链接:http://qiulyblog.github.io/2019/05/05/[题解]loj2526/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际转载请保留原文链接及作者。